The present invention relates to an error correction and detection system for a memory or storage device employed in an electronic computer or the like. In more particular, the invention relates to an error correction and detection system capable of detecting and correcting errors of 1 (m) bit and capable of detecting errors of multi-bits (more than m+1).
As an attempt to increase the reliability of memory devices, there has been used in practice an error detecting and correcting system in which so-called Hamming codes are adopted for allowing a single bit error to be detected and corrected and a double bit error to be detected. Such code is herein referred to as SEC-DED code as an abridgement form in capital letters of Single bit Error Correction - Double bit Error Detection, although the same code is sometimes referred to simply as ECC code, an abridgement of Error Check and Correction. The principle of SEC-DEC codes are fully discussed by R. W. Hamming in his article under the title "Error Detecting and Error Correcting Codes" in "The Bell System Technical Journal," Vol. XXVI, No. 2, pp. 147-160, April 1950 and also well known from U.S. Pat. No. Re. 23,601 to R. W. Hamming et al under the title "ERROR-DETECTING AND CORRECTING SYSTEM."
The principle of SEC-DEC code will be briefly reviewed. When the SEC-DED code is composed of n inherent information (data) bits in combination with k' redundant bits for error correction, the following conditions must be satisfied in order to identify the position at which the correction is required (one of n+k' positions) and detect the presence or absence of error. Namely, EQU 2.sup.k' -(n+k'+1).gtoreq.0 (1)
If one additional redundant bit is used for detecting the double bit error, the total number k of the redundant bits is equal to k'+1. Accordingly, the expression (1) can be rewritten as follows: EQU 2.sup.k-1 -(n+k).gtoreq.0 (2)
Hence, it is apparent that the total number k of the redundant bits will amount to 8 bits for the data of 64 bits (n=64).
In a practical system operative on the basis of the above principle, a write-in data of n bits is supplied to a SEC-DED code generator circuit, at which the write-in data is added with k redundant bits, whereby a write-in SEC-DED code is produced. The number of bits of this code is thus equal to n+k. The coded information containing the write-in data may then be written in a memory device. For the reading-out operation, the information as read out from the memory is a read-out SEC-DED code containing the data. The read-out information code is fed to a SEC-DED circuit in which correction of a single bit error as well as detection of double bit error are made. If a single bit error has been produced within the memory, the SEC-DED circuit detects such a single bit error, to thereby switch on a single bit error detection line for signalling an alarm signal to an operator and at the same time to correct the error bit to a correct value. When a multi-bit error greater than a double bit error, inclusive, has been produced, detection of the error is made in a similar manner and an associated multi-bit error detection line is turned on to signal an alarm. In this way, n-bits output from the SEC-DED circuit can be utilized as correct data when no error is produced within the memory or the error is a single bit.
On the other hand, when a double or more-bit error has been produced, a read-out data output from the SEC-DED circuit represents false information. For an error of 2 bits, an alarm can be produced with a probability of 100%. For an error of more than 3 bits, an alarm may be produced with a certain degree of reliability. In other words, although the generation of a double bit error can be detected without fail, perfect detection can not be expected for a multi-bit error containing 3 or more bits. Such situation is also described by Y. Hsiao in his article "A Class of Optimal Minimum Odd-weight-column SEC-DED Codes" of "IBM J. RES. DEVELOP," July 1970, pp. 395-401 (refer in particular to page 398, right column, lines 35 to 42). In such a case, the triple bit error is determined as if a single bit error were produced, whereby a miscorrection is performed. The probability of mistaking the triple bit error for a single bit error is considered generally on the order of 50 to 75%. Alternatively saying, more than half the miscorrections are processed as corrections. This is of course intolerable in a computer imposed with high reliability and accuracy requirements.
To deal with such an inconvenience, M. Y. Hsiao has introduced in the article referred to above an encoding method according to which the probability of miscorrection of the triple bit error can be reduced to a more reasonable degree.
Further, there has been proposed a system in which an undefined-bit marker circuit is added to the SEC-DED circuit for the purpose which will be mentioned below. As can be seen from the equation (2), 8 redundant bits (i.e. k=8) are required for data of 64 bits (i.e. n=64). Saying inversely, when 8 bits (k=8) are allotted for the redundant bits, the number n of the data bits may be employed up to 120 (n=120). Among the total bits of 128 in number for k=8 (i.e. n+k=128), 72 bits which are actually used are referred to as definition bits, while the remaining 56 bits are referred to as undefined bits. When a single bit error was produced, the position at which the error bit is located as detected by the SEC-DED circuit is necessarily that of a definition bit. However, where a triple bit error as produced was regarded as a single bit error, the error locations may be at positions both of the definition bits and the undefined bits. The undefined-bit marker circuit described above will be then supplied with an error bit position-designating information from the SEC-DED circuit to be examined with reference to the previously known undefined bits. With such an arrangement, it is possible to a certain degree that the triple bit error mistaken for the single bit error by the SEC-DED circuit is identified as the triple-bit error by the undefined-bit marker circuit. In other words, an error which was identified as the single-bit error in the SEC-DED circuit can be yet ascertained by the undefined bit marker circuit that the error is not in reality the single bit error.
The undefined-bit marker circuit is constituted by a combination of logic circuitries which serve for determining whether the bit as marked by the SEC-DED circuit is a previously known undefined bit or not and involves problems such as described below:
In addition to the problems described above, it should be noted that provision of the undefined-bit marker circuit at the expense of technical and economical expenditure can not assure all the false determinations of the triple bit errors being erroneously identified as the single bit errors may be completely marked to be excluded. Of course, when no undefined-bit marker circuit is provided, miscorrection will be made with a probability of 50 to 75%, as described hereinbefore. The undefined-bit marker circuit will be capable of repairing only about 45% of such miscorrections. Thus, as a whole, erroneous processing will be carried out once for every three times.
U.S. Pat. No. 3,436,734 to James H. Pomerene et al titled "ERROR CORRECTING AND REPAIRABLE DATA PROCESSING STORAGE SYSTEM" discloses a method of packing the individual bits forming words in different packages with an attempt to reduce the probability of occurrence of a triple bit error.
Further, U.S. Pat. No. 3,582,878 to Douglas C. Bossen et al entitled "MULTIPLE RANDOM ERROR CORRECTING SYSTEM," U.S. Pat. No. 3,656,107 to Mu-Yue Hsiao et al entitled "AUTOMATIC DOUBLE ERROR DETECTION AND CORRECTION APPARATUS," as well as U.S. Pat. No. 3,893,071 to Dougas C. Bossen et al entitled "MULTI-LEVEL ERROR CORRECTION SYSTEM FOR HIGH DENSITY MEMORY" disclose systems in which the number k of redundant bits employed usually in SEC-DED circuits is increased (e.g. 9 or more redundant bits for 64 data bits) thereby to allow the double or more bit error not only to be detected but also to be corrected.
Although these known methods are of great significance for enhancing the reliability, it is yet impossible to eliminate completely the miscorrections.